/ Developer CD Series 1995 August: Tool Chest / Dev.CD Aug 95 TC / Dev.CD Aug 95 TC.toast / Tool Chest / Development Tools & Languages / Macintosh Common Lisp Related / User Contributions / Conquest 1.1.sea / Conquest 1.1 / CODE / Control / conquest-primitives-2.lisp

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 1a 63 6f 6e 71 75 65 | 73 74 2d 70 72 69 6d 69 |..conque|st-primi|
|00000010| 74 69 76 65 73 2d 32 2e | 6c 69 73 70 00 00 00 00 |tives-2.|lisp....|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 43 4c | 32 01 00 00 00 00 00 00 |.TEXTCCL|2.......|
|00000050| 00 00 00 00 00 14 5a 00 | 00 01 d7 a7 aa c1 08 a7 |......Z.|........|
|00000060| aa c1 08 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 77 3e 00 00 |........|....w>..|
|00000080| 3b 3b 3b 20 63 6f 6e 71 | 75 65 73 74 2d 70 72 69 |;;; conq|uest-pri|
|00000090| 6d 69 74 69 76 65 73 2d | 32 2e 6c 69 73 70 0d 3b |mitives-|2.lisp.;|
|000000a0| 3b 3b 0d 3b 3b 3b 20 43 | 4f 4e 51 55 45 53 54 20 |;;.;;; C|ONQUEST |
|000000b0| 41 49 20 50 52 4f 4a 45 | 43 54 0d 3b 3b 3b 0d 3b |AI PROJE|CT.;;;.;|
|000000c0| 3b 3b 20 57 61 73 68 69 | 6e 67 74 6f 6e 20 55 6e |;; Washi|ngton Un|
|000000d0| 69 76 65 72 73 69 74 79 | 20 43 6f 6d 70 75 74 65 |iversity| Compute|
|000000e0| 72 20 53 63 69 65 6e 63 | 65 20 44 65 70 61 72 74 |r Scienc|e Depart|
|000000f0| 6d 65 6e 74 0d 3b 3b 3b | 20 43 6f 70 79 72 69 67 |ment.;;;| Copyrig|
|00000100| 68 74 20 31 39 39 33 20 | 50 61 75 6c 20 4d 63 43 |ht 1993 |Paul McC|
|00000110| 61 72 74 6e 65 79 2e 20 | 20 41 6c 6c 20 52 69 67 |artney. | All Rig|
|00000120| 68 74 73 20 52 65 73 65 | 72 76 65 64 2e 0d 3b 3b |hts Rese|rved..;;|
|00000130| 3b 0d 3b 3b 3b 20 41 55 | 54 48 4f 52 3a 20 20 50 |;.;;; AU|THOR:  P|
|00000140| 61 75 6c 20 4d 63 43 61 | 72 74 6e 65 79 20 0d 3b |aul McCa|rtney .;|
|00000150| 3b 3b 0d 3b 3b 3b 20 44 | 45 53 43 52 49 50 54 49 |;;.;;; D|ESCRIPTI|
|00000160| 4f 4e 3a 0d 3b 3b 3b 0d | 3b 3b 3b 20 4e 6f 6e 2d |ON:.;;;.|;;; Non-|
|00000170| 74 72 69 76 69 61 6c 20 | 50 72 69 6d 69 74 69 76 |trivial |Primitiv|
|00000180| 65 73 0d 3b 3b 3b 0d 3b | 3b 3b 20 55 53 45 3a 0d |es.;;;.;|;; USE:.|
|00000190| 3b 3b 3b 0d 0d 28 69 6e | 2d 70 61 63 6b 61 67 65 |;;;..(in|-package|
|000001a0| 20 3a 63 6f 6e 71 75 65 | 73 74 29 0d 0d 28 65 78 | :conque|st)..(ex|
|000001b0| 70 6f 72 74 20 27 28 66 | 69 6e 64 2d 63 6c 75 6d |port '(f|ind-clum|
|000001c0| 70 20 70 6c 61 79 65 72 | 2d 63 6c 75 6d 70 73 20 |p player|-clumps |
|000001d0| 66 69 6e 64 2d 6d 69 6e | 2d 70 61 74 68 73 29 0d |find-min|-paths).|
|000001e0| 20 20 20 20 20 20 20 20 | 3a 63 6f 6e 71 75 65 73 |        |:conques|
|000001f0| 74 29 0d 0d 0d 28 64 65 | 66 76 61 72 20 2a 73 65 |t)...(de|fvar *se|
|00000200| 61 72 63 68 2d 69 6e 64 | 65 78 2a 20 30 29 0d 0d |arch-ind|ex* 0)..|
|00000210| 0d 3b 3b 3b 3b 0d 3b 3b | 3b 3b 20 43 6c 75 6d 70 |.;;;;.;;|;; Clump|
|00000220| 73 0d 3b 3b 3b 3b 0d 0d | 28 64 65 66 6d 65 74 68 |s.;;;;..|(defmeth|
|00000230| 6f 64 20 66 69 6e 64 2d | 63 6c 75 6d 70 20 28 28 |od find-|clump ((|
|00000240| 70 6c 61 79 65 72 20 62 | 61 73 69 63 2d 70 6c 61 |player b|asic-pla|
|00000250| 79 65 72 29 20 63 6f 75 | 6e 74 72 79 29 0d 20 20 |yer) cou|ntry).  |
|00000260| 28 6c 65 74 20 28 28 6f | 62 20 28 63 6f 6e 74 72 |(let ((o|b (contr|
|00000270| 6f 6c 20 70 6c 61 79 65 | 72 29 29 29 0d 20 20 20 |ol playe|r))).   |
|00000280| 20 28 77 68 65 6e 20 28 | 76 61 6c 69 64 2d 63 6f | (when (|valid-co|
|00000290| 75 6e 74 72 79 2d 70 20 | 6f 62 20 63 6f 75 6e 74 |untry-p |ob count|
|000002a0| 72 79 29 0d 20 20 20 20 | 20 20 28 69 6e 63 66 20 |ry).    |  (incf |
|000002b0| 2a 73 65 61 72 63 68 2d | 69 6e 64 65 78 2a 29 0d |*search-|index*).|
|000002c0| 20 20 20 20 20 20 28 6c | 65 74 20 28 28 63 6f 75 |      (l|et ((cou|
|000002d0| 6e 74 72 79 2d 73 74 72 | 75 63 74 20 28 63 6f 75 |ntry-str|uct (cou|
|000002e0| 6e 74 72 79 2d 61 74 20 | 6f 62 20 63 6f 75 6e 74 |ntry-at |ob count|
|000002f0| 72 79 29 29 0d 20 20 20 | 20 20 20 20 20 20 20 20 |ry)).   |        |
|00000300| 20 28 6f 77 6e 65 72 20 | 28 63 6f 75 6e 74 72 79 | (owner |(country|
|00000310| 2d 6f 77 6e 65 72 20 70 | 6c 61 79 65 72 20 63 6f |-owner p|layer co|
|00000320| 75 6e 74 72 79 29 29 29 | 0d 20 20 20 20 20 20 20 |untry)))|.       |
|00000330| 20 28 66 69 6e 64 2d 63 | 6c 75 6d 70 2d 31 20 70 | (find-c|lump-1 p|
|00000340| 6c 61 79 65 72 20 6f 77 | 6e 65 72 20 63 6f 75 6e |layer ow|ner coun|
|00000350| 74 72 79 2d 73 74 72 75 | 63 74 29 29 20 29 29 29 |try-stru|ct)) )))|
|00000360| 0d 20 20 20 20 0d 0d 28 | 64 65 66 6d 65 74 68 6f |.    ..(|defmetho|
|00000370| 64 20 66 69 6e 64 2d 63 | 6c 75 6d 70 2d 31 20 28 |d find-c|lump-1 (|
|00000380| 28 70 6c 61 79 65 72 20 | 62 61 73 69 63 2d 70 6c |(player |basic-pl|
|00000390| 61 79 65 72 29 20 6f 77 | 6e 65 64 2d 62 79 20 63 |ayer) ow|ned-by c|
|000003a0| 6f 75 6e 74 72 79 29 0d | 20 20 28 73 65 74 66 20 |ountry).|  (setf |
|000003b0| 28 63 65 6c 6c 2d 61 75 | 78 20 63 6f 75 6e 74 72 |(cell-au|x countr|
|000003c0| 79 29 20 2a 73 65 61 72 | 63 68 2d 69 6e 64 65 78 |y) *sear|ch-index|
|000003d0| 2a 29 0d 20 20 28 77 68 | 65 6e 20 28 61 6e 64 20 |*).  (wh|en (and |
|000003e0| 63 6f 75 6e 74 72 79 20 | 0d 20 20 20 20 20 20 20 |country |.       |
|000003f0| 20 20 20 20 20 20 28 65 | 71 20 6f 77 6e 65 64 2d |      (e|q owned-|
|00000400| 62 79 20 28 63 65 6c 6c | 2d 6f 77 6e 65 72 20 63 |by (cell|-owner c|
|00000410| 6f 75 6e 74 72 79 29 29 | 29 0d 20 20 20 20 28 6e |ountry))|).    (n|
|00000420| 63 6f 6e 63 20 28 6c 69 | 73 74 20 28 63 65 6c 6c |conc (li|st (cell|
|00000430| 2d 70 6f 73 20 63 6f 75 | 6e 74 72 79 29 29 0d 20 |-pos cou|ntry)). |
|00000440| 20 20 20 20 20 20 20 20 | 20 20 28 6c 65 74 20 28 |        |  (let (|
|00000450| 28 72 65 73 75 6c 74 20 | 28 29 29 29 0d 20 20 20 |(result |())).   |
|00000460| 20 20 20 20 20 20 20 20 | 20 20 28 64 6f 6c 69 73 |        |  (dolis|
|00000470| 74 20 28 6e 65 69 67 68 | 62 6f 72 20 28 63 65 6c |t (neigh|bor (cel|
|00000480| 6c 2d 6e 65 69 67 68 62 | 6f 72 73 20 63 6f 75 6e |l-neighb|ors coun|
|00000490| 74 72 79 29 20 72 65 73 | 75 6c 74 29 0d 20 20 20 |try) res|ult).   |
|000004a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 28 69 66 20 |        |    (if |
|000004b0| 28 6e 65 71 20 28 63 65 | 6c 6c 2d 61 75 78 20 6e |(neq (ce|ll-aux n|
|000004c0| 65 69 67 68 62 6f 72 29 | 20 2a 73 65 61 72 63 68 |eighbor)| *search|
|000004d0| 2d 69 6e 64 65 78 2a 29 | 0d 20 20 20 20 20 20 20 |-index*)|.       |
|000004e0| 20 20 20 20 20 20 20 20 | 20 20 28 73 65 74 66 20 |        |  (setf |
|000004f0| 72 65 73 75 6c 74 20 0d | 20 20 20 20 20 20 20 20 |result .|        |
|00000500| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |        |       (|
|00000510| 6e 63 6f 6e 63 20 28 66 | 69 6e 64 2d 63 6c 75 6d |nconc (f|ind-clum|
|00000520| 70 2d 31 20 70 6c 61 79 | 65 72 20 6f 77 6e 65 64 |p-1 play|er owned|
|00000530| 2d 62 79 20 6e 65 69 67 | 68 62 6f 72 29 20 72 65 |-by neig|hbor) re|
|00000540| 73 75 6c 74 29 29 29 0d | 20 20 20 20 20 20 20 20 |sult))).|        |
|00000550| 20 20 20 20 20 20 20 29 | 29 29 20 29 29 0d 0d 0d |       )|)) ))...|
|00000560| 28 64 65 66 6d 65 74 68 | 6f 64 20 70 6c 61 79 65 |(defmeth|od playe|
|00000570| 72 2d 63 6c 75 6d 70 73 | 20 28 28 70 6c 61 79 65 |r-clumps| ((playe|
|00000580| 72 20 62 61 73 69 63 2d | 70 6c 61 79 65 72 29 20 |r basic-|player) |
|00000590| 26 6f 70 74 69 6f 6e 61 | 6c 20 28 70 6c 61 79 65 |&optiona|l (playe|
|000005a0| 72 2d 69 64 20 28 69 64 | 20 70 6c 61 79 65 72 29 |r-id (id| player)|
|000005b0| 29 29 0d 20 20 28 6c 65 | 74 20 28 28 63 6f 75 6e |)).  (le|t ((coun|
|000005c0| 74 72 69 65 73 20 28 70 | 6c 61 79 65 72 2d 63 6f |tries (p|layer-co|
|000005d0| 75 6e 74 72 69 65 73 2d | 6c 69 73 74 20 70 6c 61 |untries-|list pla|
|000005e0| 79 65 72 20 70 6c 61 79 | 65 72 2d 69 64 29 29 0d |yer play|er-id)).|
|000005f0| 20 20 20 20 20 20 20 20 | 28 63 6c 75 6d 70 73 20 |        |(clumps |
|00000600| 28 29 29 29 0d 20 20 20 | 20 28 64 6f 20 28 28 63 |())).   | (do ((c|
|00000610| 6c 75 6d 70 20 28 66 69 | 6e 64 2d 63 6c 75 6d 70 |lump (fi|nd-clump|
|00000620| 20 70 6c 61 79 65 72 20 | 28 66 69 72 73 74 20 63 | player |(first c|
|00000630| 6f 75 6e 74 72 69 65 73 | 29 29 0d 20 20 20 20 20 |ountries|)).     |
|00000640| 20 20 20 20 20 20 20 20 | 20 20 20 28 66 69 6e 64 |        |   (find|
|00000650| 2d 63 6c 75 6d 70 20 70 | 6c 61 79 65 72 20 28 66 |-clump p|layer (f|
|00000660| 69 72 73 74 20 63 6f 75 | 6e 74 72 69 65 73 29 29 |irst cou|ntries))|
|00000670| 29 29 0d 20 20 20 20 20 | 20 20 20 28 28 6e 75 6c |)).     |   ((nul|
|00000680| 6c 20 63 6f 75 6e 74 72 | 69 65 73 29 20 63 6c 75 |l countr|ies) clu|
|00000690| 6d 70 73 29 0d 20 20 20 | 20 20 20 28 70 75 73 68 |mps).   |   (push|
|000006a0| 20 63 6c 75 6d 70 20 63 | 6c 75 6d 70 73 29 0d 20 | clump c|lumps). |
|000006b0| 20 20 20 20 20 28 73 65 | 74 66 20 63 6f 75 6e 74 |     (se|tf count|
|000006c0| 72 69 65 73 20 28 73 65 | 74 2d 64 69 66 66 65 72 |ries (se|t-differ|
|000006d0| 65 6e 63 65 20 63 6f 75 | 6e 74 72 69 65 73 20 63 |ence cou|ntries c|
|000006e0| 6c 75 6d 70 29 29 29 20 | 29 29 0d 0d 0d 3b 3b 3b |lump))) |))...;;;|
|000006f0| 3b 0d 3b 3b 3b 3b 20 50 | 61 74 68 73 0d 3b 3b 3b |;.;;;; P|aths.;;;|
|00000700| 3b 0d 0d 28 64 65 66 6d | 65 74 68 6f 64 20 66 69 |;..(defm|ethod fi|
|00000710| 6e 64 2d 6d 69 6e 2d 70 | 61 74 68 73 20 28 28 70 |nd-min-p|aths ((p|
|00000720| 6c 61 79 65 72 20 62 61 | 73 69 63 2d 70 6c 61 79 |layer ba|sic-play|
|00000730| 65 72 29 20 66 72 6f 6d | 2d 63 6f 75 6e 74 72 79 |er) from|-country|
|00000740| 20 74 6f 2d 63 6f 75 6e | 74 72 69 65 73 20 0d 20 | to-coun|tries . |
|00000750| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000760| 20 20 20 20 20 20 20 20 | 20 20 26 6f 70 74 69 6f |        |  &optio|
|00000770| 6e 61 6c 20 28 61 76 6f | 69 64 2d 70 6c 61 79 65 |nal (avo|id-playe|
|00000780| 72 73 20 28 6c 69 73 74 | 20 28 69 64 20 70 6c 61 |rs (list| (id pla|
|00000790| 79 65 72 29 29 29 29 0d | 20 20 28 6c 65 74 2a 20 |yer)))).|  (let* |
|000007a0| 28 28 6f 62 20 28 63 6f | 6e 74 72 6f 6c 20 70 6c |((ob (co|ntrol pl|
|000007b0| 61 79 65 72 29 29 0d 20 | 20 20 20 20 20 20 20 20 |ayer)). |        |
|000007c0| 28 63 6f 75 6e 74 72 79 | 20 28 63 6f 75 6e 74 72 |(country| (countr|
|000007d0| 79 2d 61 74 20 6f 62 20 | 66 72 6f 6d 2d 63 6f 75 |y-at ob |from-cou|
|000007e0| 6e 74 72 79 29 29 29 0d | 20 20 20 20 28 77 68 65 |ntry))).|    (whe|
|000007f0| 6e 20 63 6f 75 6e 74 72 | 79 0d 20 20 20 20 20 20 |n countr|y.      |
|00000800| 28 69 6e 63 66 20 2a 73 | 65 61 72 63 68 2d 69 6e |(incf *s|earch-in|
|00000810| 64 65 78 2a 29 0d 20 20 | 20 20 20 20 28 73 65 74 |dex*).  |    (set|
|00000820| 66 20 28 63 65 6c 6c 2d | 61 75 78 20 63 6f 75 6e |f (cell-|aux coun|
|00000830| 74 72 79 29 20 2a 73 65 | 61 72 63 68 2d 69 6e 64 |try) *se|arch-ind|
|00000840| 65 78 2a 29 0d 20 20 20 | 20 20 20 28 73 65 74 66 |ex*).   |   (setf|
|00000850| 20 28 63 65 6c 6c 2d 63 | 6f 73 74 20 63 6f 75 6e | (cell-c|ost coun|
|00000860| 74 72 79 29 20 30 29 0d | 0d 20 20 20 20 20 20 28 |try) 0).|.      (|
|00000870| 6c 65 74 2a 20 28 28 6e | 65 69 67 68 62 6f 72 73 |let* ((n|eighbors|
|00000880| 20 28 63 65 6c 6c 2d 6e | 65 69 67 68 62 6f 72 73 | (cell-n|eighbors|
|00000890| 20 63 6f 75 6e 74 72 79 | 29 29 0d 20 20 20 20 20 | country|)).     |
|000008a0| 20 20 20 20 20 20 20 20 | 28 6d 65 61 6e 2d 6e 65 |        |(mean-ne|
|000008b0| 69 67 68 62 6f 72 73 20 | 0d 20 20 20 20 20 20 20 |ighbors |.       |
|000008c0| 20 20 20 20 20 20 20 28 | 72 65 6d 6f 76 65 2d 69 |       (|remove-i|
|000008d0| 66 20 23 27 28 6c 61 6d | 62 64 61 20 28 6e 65 69 |f #'(lam|bda (nei|
|000008e0| 67 68 62 6f 72 29 0d 20 | 20 20 20 20 20 20 20 20 |ghbor). |        |
|000008f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000900| 20 20 20 20 28 6d 65 6d | 62 65 72 20 28 63 65 6c |    (mem|ber (cel|
|00000910| 6c 2d 6f 77 6e 65 72 20 | 6e 65 69 67 68 62 6f 72 |l-owner |neighbor|
|00000920| 29 20 61 76 6f 69 64 2d | 70 6c 61 79 65 72 73 29 |) avoid-|players)|
|00000930| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|00000940| 20 20 20 20 20 20 20 20 | 20 20 20 6e 65 69 67 68 |        |   neigh|
|00000950| 62 6f 72 73 29 29 29 0d | 20 20 20 20 20 20 20 20 |bors))).|        |
|00000960| 28 64 6f 6c 69 73 74 20 | 28 6e 65 69 67 68 62 6f |(dolist |(neighbo|
|00000970| 72 20 6d 65 61 6e 2d 6e | 65 69 67 68 62 6f 72 73 |r mean-n|eighbors|
|00000980| 29 0d 20 20 20 20 20 20 | 20 20 20 20 28 73 65 74 |).      |    (set|
|00000990| 66 20 28 63 65 6c 6c 2d | 63 6f 73 74 20 6e 65 69 |f (cell-|cost nei|
|000009a0| 67 68 62 6f 72 29 20 28 | 63 65 6c 6c 2d 6e 2d 61 |ghbor) (|cell-n-a|
|000009b0| 72 6d 69 65 73 20 6e 65 | 69 67 68 62 6f 72 29 29 |rmies ne|ighbor))|
|000009c0| 0d 20 20 20 20 20 20 20 | 20 20 20 28 73 65 74 66 |.       |   (setf|
|000009d0| 20 28 63 65 6c 6c 2d 61 | 75 78 20 6e 65 69 67 68 | (cell-a|ux neigh|
|000009e0| 62 6f 72 29 20 2a 73 65 | 61 72 63 68 2d 69 6e 64 |bor) *se|arch-ind|
|000009f0| 65 78 2a 29 0d 20 20 20 | 20 20 20 20 20 20 20 28 |ex*).   |       (|
|00000a00| 63 6f 6d 70 75 74 65 2d | 70 61 74 68 2d 6c 65 6e |compute-|path-len|
|00000a10| 67 74 68 73 20 70 6c 61 | 79 65 72 20 6e 65 69 67 |gths pla|yer neig|
|00000a20| 68 62 6f 72 20 61 76 6f | 69 64 2d 70 6c 61 79 65 |hbor avo|id-playe|
|00000a30| 72 73 20 74 29 29 20 29 | 0d 0d 20 20 20 20 20 20 |rs t)) )|..      |
|00000a40| 28 6c 65 74 20 28 28 70 | 61 74 68 73 20 0d 20 20 |(let ((p|aths .  |
|00000a50| 20 20 20 20 20 20 20 20 | 20 20 20 28 6d 61 70 63 |        |   (mapc|
|00000a60| 61 72 20 23 27 28 6c 61 | 6d 62 64 61 20 28 74 6f |ar #'(la|mbda (to|
|00000a70| 2d 63 6f 75 6e 74 72 79 | 29 0d 20 20 20 20 20 20 |-country|).      |
|00000a80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000a90| 20 20 20 28 6c 65 74 2a | 20 28 28 63 6f 75 6e 74 |   (let*| ((count|
|00000aa0| 72 79 20 28 63 6f 75 6e | 74 72 79 2d 61 74 20 6f |ry (coun|try-at o|
|00000ab0| 62 20 74 6f 2d 63 6f 75 | 6e 74 72 79 29 29 0d 20 |b to-cou|ntry)). |
|00000ac0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000ad0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |        |       (|
|00000ae0| 70 61 74 68 20 28 6e 72 | 65 76 65 72 73 65 20 28 |path (nr|everse (|
|00000af0| 66 69 6e 64 2d 70 61 74 | 68 20 70 6c 61 79 65 72 |find-pat|h player|
|00000b00| 20 63 6f 75 6e 74 72 79 | 29 29 29 0d 20 20 20 20 | country|))).    |
|00000b10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000b20| 20 20 20 20 20 20 20 20 | 20 20 20 20 28 63 6f 73 |        |    (cos|
|00000b30| 74 20 28 69 66 20 70 61 | 74 68 0d 20 20 20 20 20 |t (if pa|th.     |
|00000b40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000b50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000b60| 20 20 20 28 63 65 6c 6c | 2d 63 6f 73 74 20 63 6f |   (cell|-cost co|
|00000b70| 75 6e 74 72 79 29 29 29 | 29 0d 20 20 20 20 20 20 |untry)))|).      |
|00000b80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000b90| 20 20 20 20 20 28 6c 69 | 73 74 20 63 6f 73 74 20 |     (li|st cost |
|00000ba0| 70 61 74 68 29 29 29 0d | 20 20 20 20 20 20 20 20 |path))).|        |
|00000bb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 74 6f 2d |        |     to-|
|00000bc0| 63 6f 75 6e 74 72 69 65 | 73 29 29 29 0d 20 20 20 |countrie|s))).   |
|00000bd0| 20 20 20 20 20 28 64 65 | 6c 65 74 65 2d 69 66 20 |     (de|lete-if |
|00000be0| 23 27 28 6c 61 6d 62 64 | 61 20 28 70 61 74 68 29 |#'(lambd|a (path)|
|00000bf0| 20 28 6e 75 6c 6c 20 28 | 66 69 72 73 74 20 70 61 | (null (|first pa|
|00000c00| 74 68 29 29 29 20 70 61 | 74 68 73 29 20 29 29 29 |th))) pa|ths) )))|
|00000c10| 29 0d 0d 0d 28 64 65 66 | 6d 65 74 68 6f 64 20 63 |)...(def|method c|
|00000c20| 6f 6d 70 75 74 65 2d 70 | 61 74 68 2d 6c 65 6e 67 |ompute-p|ath-leng|
|00000c30| 74 68 73 20 28 28 70 6c | 61 79 65 72 20 62 61 73 |ths ((pl|ayer bas|
|00000c40| 69 63 2d 70 6c 61 79 65 | 72 29 20 63 6f 75 6e 74 |ic-playe|r) count|
|00000c50| 72 79 20 61 6c 6c 69 65 | 73 20 6e 65 77 2d 73 74 |ry allie|s new-st|
|00000c60| 61 72 74 29 0d 20 20 28 | 64 65 63 6c 61 72 65 20 |art).  (|declare |
|00000c70| 28 6f 70 74 69 6d 69 7a | 65 20 28 73 70 65 65 64 |(optimiz|e (speed|
|00000c80| 20 33 29 20 28 73 61 66 | 65 74 79 20 30 29 20 28 | 3) (saf|ety 0) (|
|00000c90| 73 70 61 63 65 20 30 29 | 29 29 0d 20 20 28 6c 65 |space 0)|)).  (le|
|00000ca0| 74 2a 20 28 28 6e 65 69 | 67 68 62 6f 72 73 20 28 |t* ((nei|ghbors (|
|00000cb0| 63 65 6c 6c 2d 6e 65 69 | 67 68 62 6f 72 73 20 63 |cell-nei|ghbors c|
|00000cc0| 6f 75 6e 74 72 79 29 29 | 0d 20 20 20 20 20 20 20 |ountry))|.       |
|00000cd0| 20 20 28 6d 65 61 6e 2d | 6e 65 69 67 68 62 6f 72 |  (mean-|neighbor|
|00000ce0| 73 20 28 72 65 6d 6f 76 | 65 2d 69 66 20 23 27 28 |s (remov|e-if #'(|
|00000cf0| 6c 61 6d 62 64 61 20 28 | 6e 65 69 67 68 62 6f 72 |lambda (|neighbor|
|00000d00| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|00000d10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000d20| 20 20 20 20 20 20 20 20 | 20 20 28 6d 65 6d 62 65 |        |  (membe|
|00000d30| 72 20 28 63 65 6c 6c 2d | 6f 77 6e 65 72 20 6e 65 |r (cell-|owner ne|
|00000d40| 69 67 68 62 6f 72 29 20 | 61 6c 6c 69 65 73 29 29 |ighbor) |allies))|
|00000d50| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|00000d60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000d70| 20 20 20 20 20 6e 65 69 | 67 68 62 6f 72 73 29 29 |     nei|ghbors))|
|00000d80| 20 0d 20 20 20 20 20 20 | 20 20 20 28 63 6f 6d 70 | .      |   (comp|
|00000d90| 75 74 65 64 2d 6e 65 69 | 67 68 62 6f 72 73 20 28 |uted-nei|ghbors (|
|00000da0| 72 65 6d 6f 76 65 2d 69 | 66 20 23 27 28 6c 61 6d |remove-i|f #'(lam|
|00000db0| 62 64 61 20 28 6e 65 69 | 67 68 62 6f 72 29 0d 20 |bda (nei|ghbor). |
|00000dc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000de0| 20 20 20 20 20 20 20 20 | 20 20 20 28 6e 6f 74 20 |        |   (not |
|00000df0| 28 65 71 20 2a 73 65 61 | 72 63 68 2d 69 6e 64 65 |(eq *sea|rch-inde|
|00000e00| 78 2a 20 28 63 65 6c 6c | 2d 61 75 78 20 6e 65 69 |x* (cell|-aux nei|
|00000e10| 67 68 62 6f 72 29 29 29 | 29 0d 20 20 20 20 20 20 |ghbor)))|).      |
|00000e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000e30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000e40| 20 20 6d 65 61 6e 2d 6e | 65 69 67 68 62 6f 72 73 |  mean-n|eighbors|
|00000e50| 29 29 0d 20 20 20 20 20 | 20 20 20 20 28 6d 69 6e |)).     |    (min|
|00000e60| 20 6d 6f 73 74 2d 70 6f | 73 69 74 69 76 65 2d 66 | most-po|sitive-f|
|00000e70| 69 78 6e 75 6d 29 0d 20 | 20 20 20 20 20 20 20 20 |ixnum). |        |
|00000e80| 28 6f 6c 64 2d 69 6e 64 | 65 78 20 28 63 65 6c 6c |(old-ind|ex (cell|
|00000e90| 2d 61 75 78 20 63 6f 75 | 6e 74 72 79 29 29 0d 20 |-aux cou|ntry)). |
|00000ea0| 20 20 20 20 20 20 20 20 | 28 6f 6c 64 2d 6d 69 6e |        |(old-min|
|00000eb0| 20 28 69 66 20 28 65 71 | 20 28 63 65 6c 6c 2d 61 | (if (eq| (cell-a|
|00000ec0| 75 78 20 63 6f 75 6e 74 | 72 79 29 20 2a 73 65 61 |ux count|ry) *sea|
|00000ed0| 72 63 68 2d 69 6e 64 65 | 78 2a 29 0d 20 20 20 20 |rch-inde|x*).    |
|00000ee0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000ef0| 28 63 65 6c 6c 2d 63 6f | 73 74 20 63 6f 75 6e 74 |(cell-co|st count|
|00000f00| 72 79 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ry).    |        |
|00000f10| 20 20 20 20 20 20 20 20 | 6d 6f 73 74 2d 70 6f 73 |        |most-pos|
|00000f20| 69 74 69 76 65 2d 66 69 | 78 6e 75 6d 29 29 29 0d |itive-fi|xnum))).|
|00000f30| 20 20 20 20 0d 20 20 20 | 20 28 64 6f 6c 69 73 74 |    .   | (dolist|
|00000f40| 20 28 6e 65 69 67 68 62 | 6f 72 20 63 6f 6d 70 75 | (neighb|or compu|
|00000f50| 74 65 64 2d 6e 65 69 67 | 68 62 6f 72 73 29 0d 20 |ted-neig|hbors). |
|00000f60| 20 20 20 20 20 28 6c 65 | 74 20 28 28 63 6f 73 74 |     (le|t ((cost|
|00000f70| 20 28 2b 20 28 63 65 6c | 6c 2d 63 6f 73 74 20 6e | (+ (cel|l-cost n|
|00000f80| 65 69 67 68 62 6f 72 29 | 20 28 63 65 6c 6c 2d 6e |eighbor)| (cell-n|
|00000f90| 2d 61 72 6d 69 65 73 20 | 63 6f 75 6e 74 72 79 29 |-armies |country)|
|00000fa0| 29 29 29 0d 20 20 20 20 | 20 20 20 20 28 69 66 20 |))).    |    (if |
|00000fb0| 28 3e 20 6d 69 6e 20 63 | 6f 73 74 29 0d 20 20 20 |(> min c|ost).   |
|00000fc0| 20 20 20 20 20 20 20 28 | 73 65 74 66 20 6d 69 6e |       (|setf min|
|00000fd0| 20 63 6f 73 74 29 29 29 | 29 0d 20 20 20 20 0d 20 | cost)))|).    . |
|00000fe0| 20 20 20 28 73 65 74 66 | 20 28 63 65 6c 6c 2d 63 |   (setf| (cell-c|
|00000ff0| 6f 73 74 20 63 6f 75 6e | 74 72 79 29 20 28 6d 69 |ost coun|try) (mi|
|00001000| 6e 20 6d 69 6e 20 6f 6c | 64 2d 6d 69 6e 29 29 0d |n min ol|d-min)).|
|00001010| 20 20 20 20 28 73 65 74 | 66 20 28 63 65 6c 6c 2d |    (set|f (cell-|
|00001020| 61 75 78 20 63 6f 75 6e | 74 72 79 29 20 2a 73 65 |aux coun|try) *se|
|00001030| 61 72 63 68 2d 69 6e 64 | 65 78 2a 29 0d 0d 20 20 |arch-ind|ex*)..  |
|00001040| 20 20 28 77 68 65 6e 20 | 28 6f 72 20 6e 65 77 2d |  (when |(or new-|
|00001050| 73 74 61 72 74 20 28 6e | 65 71 20 6f 6c 64 2d 69 |start (n|eq old-i|
|00001060| 6e 64 65 78 20 2a 73 65 | 61 72 63 68 2d 69 6e 64 |ndex *se|arch-ind|
|00001070| 65 78 2a 29 29 0d 20 20 | 20 20 20 20 28 64 6f 6c |ex*)).  |    (dol|
|00001080| 69 73 74 20 28 6e 65 69 | 67 68 62 6f 72 20 6d 65 |ist (nei|ghbor me|
|00001090| 61 6e 2d 6e 65 69 67 68 | 62 6f 72 73 29 0d 20 20 |an-neigh|bors).  |
|000010a0| 20 20 20 20 20 20 28 63 | 6f 6d 70 75 74 65 2d 70 |      (c|ompute-p|
|000010b0| 61 74 68 2d 6c 65 6e 67 | 74 68 73 20 70 6c 61 79 |ath-leng|ths play|
|000010c0| 65 72 20 6e 65 69 67 68 | 62 6f 72 20 61 6c 6c 69 |er neigh|bor alli|
|000010d0| 65 73 20 6e 69 6c 29 29 | 29 0d 20 20 20 20 0d 20 |es nil))|).    . |
|000010e0| 20 20 20 28 77 68 65 6e | 20 28 61 6e 64 20 28 6e |   (when| (and (n|
|000010f0| 6f 74 20 6e 65 77 2d 73 | 74 61 72 74 29 20 28 3c |ot new-s|tart) (<|
|00001100| 20 28 63 65 6c 6c 2d 63 | 6f 73 74 20 63 6f 75 6e | (cell-c|ost coun|
|00001110| 74 72 79 29 20 6f 6c 64 | 2d 6d 69 6e 29 29 0d 20 |try) old|-min)). |
|00001120| 20 20 20 20 20 28 64 6f | 6c 69 73 74 20 28 6e 65 |     (do|list (ne|
|00001130| 69 67 68 62 6f 72 20 63 | 6f 6d 70 75 74 65 64 2d |ighbor c|omputed-|
|00001140| 6e 65 69 67 68 62 6f 72 | 73 29 0d 20 20 20 20 20 |neighbor|s).     |
|00001150| 20 20 20 28 63 6f 6d 70 | 75 74 65 2d 70 61 74 68 |   (comp|ute-path|
|00001160| 2d 6c 65 6e 67 74 68 73 | 20 70 6c 61 79 65 72 20 |-lengths| player |
|00001170| 6e 65 69 67 68 62 6f 72 | 20 61 6c 6c 69 65 73 20 |neighbor| allies |
|00001180| 6e 69 6c 29 29 29 20 29 | 29 0d 0d 0d 28 64 65 66 |nil))) )|)...(def|
|00001190| 6d 65 74 68 6f 64 20 66 | 69 6e 64 2d 70 61 74 68 |method f|ind-path|
|000011a0| 20 28 28 70 6c 61 79 65 | 72 20 62 61 73 69 63 2d | ((playe|r basic-|
|000011b0| 70 6c 61 79 65 72 29 20 | 63 6f 75 6e 74 72 79 29 |player) |country)|
|000011c0| 0d 20 20 28 64 65 63 6c | 61 72 65 20 28 6f 70 74 |.  (decl|are (opt|
|000011d0| 69 6d 69 7a 65 20 28 73 | 70 65 65 64 20 33 29 20 |imize (s|peed 3) |
|000011e0| 28 73 61 66 65 74 79 20 | 30 29 20 28 73 70 61 63 |(safety |0) (spac|
|000011f0| 65 20 30 29 29 29 0d 20 | 20 28 77 68 65 6e 20 28 |e 0))). | (when (|
|00001200| 61 6e 64 20 63 6f 75 6e | 74 72 79 20 28 65 71 20 |and coun|try (eq |
|00001210| 28 63 65 6c 6c 2d 61 75 | 78 20 63 6f 75 6e 74 72 |(cell-au|x countr|
|00001220| 79 29 20 2a 73 65 61 72 | 63 68 2d 69 6e 64 65 78 |y) *sear|ch-index|
|00001230| 2a 29 29 0d 20 20 20 20 | 28 6c 65 74 2a 20 28 28 |*)).    |(let* ((|
|00001240| 6d 69 6e 20 6d 6f 73 74 | 2d 70 6f 73 69 74 69 76 |min most|-positiv|
|00001250| 65 2d 66 69 78 6e 75 6d | 29 0d 20 20 20 20 20 20 |e-fixnum|).      |
|00001260| 20 20 20 20 20 28 6d 69 | 6e 2d 6e 65 69 67 68 62 |     (mi|n-neighb|
|00001270| 6f 72 20 6e 69 6c 29 0d | 20 20 20 20 20 20 20 20 |or nil).|        |
|00001280| 20 20 20 28 6e 65 69 67 | 68 62 6f 72 73 20 28 63 |   (neig|hbors (c|
|00001290| 65 6c 6c 2d 6e 65 69 67 | 68 62 6f 72 73 20 63 6f |ell-neig|hbors co|
|000012a0| 75 6e 74 72 79 29 29 0d | 20 20 20 20 20 20 20 20 |untry)).|        |
|000012b0| 20 20 20 28 73 65 67 6d | 65 6e 74 20 28 6c 69 73 |   (segm|ent (lis|
|000012c0| 74 20 28 63 65 6c 6c 2d | 70 6f 73 20 63 6f 75 6e |t (cell-|pos coun|
|000012d0| 74 72 79 29 29 29 29 0d | 20 20 20 20 20 20 0d 20 |try)))).|      . |
|000012e0| 20 20 20 20 20 28 63 6f | 6e 64 20 28 28 3d 20 28 |     (co|nd ((= (|
|000012f0| 63 65 6c 6c 2d 63 6f 73 | 74 20 63 6f 75 6e 74 72 |cell-cos|t countr|
|00001300| 79 29 20 28 63 65 6c 6c | 2d 6e 2d 61 72 6d 69 65 |y) (cell|-n-armie|
|00001310| 73 20 63 6f 75 6e 74 72 | 79 29 29 20 73 65 67 6d |s countr|y)) segm|
|00001320| 65 6e 74 29 0d 20 20 20 | 20 20 20 20 20 20 20 20 |ent).   |        |
|00001330| 20 28 74 20 0d 20 20 20 | 20 20 20 20 20 20 20 20 | (t .   |        |
|00001340| 20 20 28 64 6f 6c 69 73 | 74 20 28 6e 65 69 67 68 |  (dolis|t (neigh|
|00001350| 62 6f 72 20 6e 65 69 67 | 68 62 6f 72 73 29 0d 20 |bor neig|hbors). |
|00001360| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 6c |        |      (l|
|00001370| 65 74 2a 20 28 28 63 6f | 73 74 20 28 63 65 6c 6c |et* ((co|st (cell|
|00001380| 2d 63 6f 73 74 20 6e 65 | 69 67 68 62 6f 72 29 29 |-cost ne|ighbor))|
|00001390| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|000013a0| 20 20 20 20 20 20 20 28 | 61 75 78 20 28 63 65 6c |       (|aux (cel|
|000013b0| 6c 2d 61 75 78 20 6e 65 | 69 67 68 62 6f 72 29 29 |l-aux ne|ighbor))|
|000013c0| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|000013d0| 20 20 20 28 77 68 65 6e | 20 28 61 6e 64 20 28 65 |   (when| (and (e|
|000013e0| 71 20 2a 73 65 61 72 63 | 68 2d 69 6e 64 65 78 2a |q *searc|h-index*|
|000013f0| 20 61 75 78 29 0d 20 20 | 20 20 20 20 20 20 20 20 | aux).  |        |
|00001400| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001410| 20 20 63 6f 73 74 20 0d | 20 20 20 20 20 20 20 20 |  cost .|        |
|00001420| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001430| 20 20 20 20 28 3e 20 6d | 69 6e 20 63 6f 73 74 29 |    (> m|in cost)|
|00001440| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|00001450| 20 20 20 20 20 28 73 65 | 74 66 20 6d 69 6e 20 63 |     (se|tf min c|
|00001460| 6f 73 74 29 0d 20 20 20 | 20 20 20 20 20 20 20 20 |ost).   |        |
|00001470| 20 20 20 20 20 20 20 20 | 28 73 65 74 66 20 6d 69 |        |(setf mi|
|00001480| 6e 2d 6e 65 69 67 68 62 | 6f 72 20 6e 65 69 67 68 |n-neighb|or neigh|
|00001490| 62 6f 72 29 29 29 29 0d | 20 20 20 20 20 20 20 20 |bor)))).|        |
|000014a0| 20 20 20 20 20 28 6e 63 | 6f 6e 63 20 73 65 67 6d |     (nc|onc segm|
|000014b0| 65 6e 74 20 28 66 69 6e | 64 2d 70 61 74 68 20 70 |ent (fin|d-path p|
|000014c0| 6c 61 79 65 72 20 6d 69 | 6e 2d 6e 65 69 67 68 62 |layer mi|n-neighb|
|000014d0| 6f 72 29 29 20 29 29 29 | 29 29 00 00 00 00 00 00 |or)) )))|))......|
|000014e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000014f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001500| 00 00 01 00 00 00 01 85 | 00 00 00 85 00 00 00 52 |........|.......R|
|00001510| 00 78 14 f5 ea a5 02 9a | f4 af 2d 16 ba 89 f7 8b |.x......|..-.....|
|00001520| 8e 84 ad 9a 3b 02 8d dc | 76 04 8d 0b 50 8d 0e c4 |....;...|v...P...|
|00001530| 1a 63 6f 6e 71 75 65 73 | 74 2d 70 72 69 6d 69 74 |.conques|t-primit|
|00001540| 69 76 65 73 2d 32 2e 6c | 69 73 70 6d 02 00 00 00 |ives-2.l|ispm....|
|00001550| 00 00 54 45 58 54 43 43 | 4c 32 01 00 00 64 00 00 |..TEXTCC|L2...d..|
|00001560| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001570| 00 00 a7 a3 fb 70 00 00 | 14 5a 00 00 01 d7 21 f0 |.....p..|.Z....!.|
|00001580| 00 01 00 01 11 8d ef e9 | bb 7a 93 02 bf f5 92 85 |........|.z......|
|00001590| 00 f3 ae d9 b2 41 01 a9 | 02 03 00 00 02 05 04 04 |.....A..|........|
|000015a0| 6f 31 6b 00 00 01 04 27 | 01 8d 13 d0 fa a6 86 00 |o1k....'|........|
|000015b0| 2a 01 2c 0c 9d f6 8d 0b | c4 f3 f5 a2 4d 03 c1 c9 |*.,.....|....M...|
|000015c0| f4 67 56 f6 f3 f5 b2 6a | 00 bd 67 10 f6 f3 f5 d2 |.gV....j|..g.....|
|000015d0| 31 01 ce 8d 0f cc f6 f3 | f5 1a 49 00 92 bd a9 ce |1.......|..I.....|
|000015e0| 85 bf f5 72 4b 03 f6 f3 | f5 5a 45 02 f3 f5 72 c1 |...rK...|.ZE...r.|
|000015f0| 00 ce bf f5 7a 04 02 ac | ae 82 00 60 ff f8 cf 9a |....z...|...`....|
|00001600| 00 00 00 48 00 09 4d 6f | 6e 61 63 6f 00 00 00 00 |...H..Mo|naco....|
|00001610| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001620| 00 00 00 00 00 00 00 06 | 00 08 00 27 00 0b 01 df |........|...'....|
|00001630| 02 42 00 27 00 0b 01 df | 02 42 00 00 00 00 00 00 |.B.'....|.B......|
|00001640| 11 09 00 00 11 09 00 00 | 0c 49 01 00 00 00 00 0f |........|.I......|
|00001650| 00 15 05 54 69 6d 65 73 | 06 4d 6f 6e 61 63 6f 00 |...Times|.Monaco.|
|00001660| 00 00 22 00 02 00 14 0c | 01 00 04 09 00 01 00 00 |..".....|........|
|00001670| 00 02 00 01 14 01 00 01 | 91 02 00 01 a7 01 00 06 |........|........|
|00001680| 6d 02 00 06 82 00 00 01 | 00 00 00 01 85 00 00 00 |m.......|........|
|00001690| 85 00 00 00 52 00 19 a7 | 8c 0a a8 00 00 00 1c 00 |....R...|........|
|000016a0| 52 00 01 46 52 45 44 00 | 01 00 12 4d 50 53 52 00 |R..FRED.|...MPSR.|
|000016b0| 00 00 2a 00 02 ff ff 00 | 00 00 5f 00 00 00 00 00 |..*.....|.._.....|
|000016c0| 03 ff ff 00 00 00 4c 00 | 00 00 00 03 ed ff ff 00 |......L.|........|
|000016d0| 00 00 00 00 1a 94 80 00 | 00 00 00 00 00 00 00 00 |........|........|
|000016e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000016f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+